package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.ArrayProblem;
import cn.pugle.oj.catalog.Unknown;

import java.util.*;

/**
 * https://leetcode.com/problems/3sum/
 * Runtime: 619 ms
 *
 * @author tzp
 * @since 2020/9/14
 */
public class LC15 implements ArrayProblem {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> result = new HashSet<>();
        Map<Integer, List<Integer>> cache = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            cache.compute(nums[i], (newIndex, olds) -> {
                if (olds == null) {
                    olds = new ArrayList<>();
                }
                olds.add(newIndex);
                return olds;
            });
        }

        for (Map.Entry<Integer, List<Integer>> e1 : cache.entrySet()) {
            for (Map.Entry<Integer, List<Integer>> e2 : cache.entrySet()) {
                int k3 = -e1.getKey() - e2.getKey();
                List<Integer> v3 = cache.get(k3);

                int need1 = 1, need2 = 1, need3 = 1;
                if (e1.getKey().equals(e2.getKey())) {
                    need1++;
                    need2++;
                }
                if (e1.getKey().equals(k3)) {
                    need1++;
                    need3++;
                }
                if (e2.getKey().equals(k3)) {
                    need2++;
                    need3++;
                }
                if (v3 != null
                        && e1.getValue().size() >= need1
                        && e2.getValue().size() >= need2
                        && v3.size() >= need3) {
                    List<Integer> x = Arrays.asList(e1.getKey(), e2.getKey(), k3);
                    x.sort(Integer::compareTo);
                    result.add(x);
                }
            }
        }


//        for (int i = 0; i < nums.length; i++) {
//            for (int j = i + 1; j < nums.length; j++) {
//                int extra = -nums[i] - nums[j];
//                int need = 1;
//                if (extra == nums[i]) {
//                    need++;
//                }
//                if (extra == nums[j]) {
//                    need++;
//                }
//                List<Integer> indices = cache.get(extra);
//                if (indices != null && indices.size() >= need) {
//                    List<Integer> x = Arrays.asList(nums[i], nums[j], extra);
//                    x.sort(Integer::compareTo);
//                    result.add(x);
//                }
//            }
//        }
        return new ArrayList<>(result);
    }

    public static void main(String[] args) {
        System.out.println(new LC15().threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }

}
